Search Results

  1. J. Nousiainen, Forwarding capacity of an infinite homogeneous wireless network, Helsinki University of Technology, 2008, Master's Thesis (pdf)(bib)
    Abstract: An ad hoc network is a wireless network independent of any fixed infrastructure where the nodes communicate with each other in a multihop fashion. In the absence of centralized control, the nodes are responsible for all network activity, which includes discovering the route to the destination and forwarding packets towards it. We begin this thesis with a short introduction to ad hoc networks and the factors affecting their performance, namely medium access control (MAC) and routing. We also consider wireless sensor networks (WSN), a special case of ad hoc networks, that other a wide range of proposed applications for large ad hoc networks. When the ad hoc network is very large, the macroscopic level, corresponding to the scale of an end-to-end path, and the microscopic level, corresponding to the scale of a single hop, can be separated. The macroscopic level routing protocol, treating the network as a continuous medium, provides the direction of packet flow to the microscopic level where the packets are forwarded based on this information according to the rules of the microscopic level forwarding method. Considering one direction at a time, there exists a certain maximum flow of packets that can be supported. Generally, this maximal sustainable directed packet flow depends on the network properties and the used medium access control (MAC) protocol. The capacity of the network can be divided between different direction, e.g., via time sharing. In the main contribution of the thesis, we model a large ad hoc network and devise a simulation algorithm for obtaining an upper bound for the maximal forwarding capacity under that model. The Moving window algorithm (MWA) that is based on an augmentation of the max-flow min-cut theorem is then improved to produce tighter upper bounds for the maximal capacity. The results are compared to the capacities of existing forwarding methods, providing feasible lower bounds, and the optimal capacities of networks with regular structure. The tightest obtained upper bound is about three times the maximum performance achieved with existing forwarding methods.